package leetcode.动态规划和贪心;

/**
 * 最长回文子串（动态规划和贪心）
 *
 * 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
 *
 * 示例 1：
 *
 * 输入: "babad"
 * 输出: "bab"
 * 注意: "aba" 也是一个有效答案。
 * 示例 2：
 *
 * 输入: "cbbd"
 * 输出: "bb"
 */
public class Test5最长回文子串 {

    public static String longestPalindrome(String s) {
        String ans = null;
        // 先排除特殊情况
        if (s.equals("") || s == null) {
            return "";
        }
        int len1 = 0, len2 = 0, len = 0, start = 0, end = 0;
        // 把字符串的每一个字符都拿出来与他左右两边剩余的字符比较
        for (int i = 0; i < s.length(); i++) {
            // 字符个数为奇数时
            len1 = maxLength(s, i, i, len1);
            // 字符个数为偶数时
            len2 = maxLength(s, i, i+1, len2);
            // 获得最大的回文字符串长度
            len = Math.max(len1, len2);
            if (len > (end - start + 1)) {
                // 通过回文字符串长度的一半计算起始点离当前 i 的距离
                start = i - (len - 1 ) / 2; // len - 1是为了消除start会前移动1个位置的影响
                if (start < 0) {
                    start = 0;
                }
                end = i + (len / 2);
                if (end > s.length()) {
                    end = s.length();
                }
            }
        }
        return s.substring(start, end + 1);
    }

    public static int maxLength(String s, int left, int right, int len) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            // 由中心向两边扩散检查
            left--;
            right++;
        }
        if (len <= (right - left - 1)) {
            // 因为left最后会变为-1，减去-1相当于加一，所以要减掉这个1
            return right - left - 1;
        } else {
            return len;
        }
    }

    public static void main(String[] args) {
        // 测试用例很重要！多想一些用例测试
        //System.out.println(longestPalindrome("babadada"));
        System.out.println(longestPalindrome2("babadada"));
    }

    /**
     * 动态规划进行记忆化搜索，dp最重要的是写出状态转移方程。
     *
     * dp[i][j]表示区间[i,j]是否为回文串,那么有如下状态转移方程：
     *
     * i = j, 即一个字符的时候，dp[i][i] = true；
     *
     * i - j = 1时：当且仅当两个字符相等的时候，是回文字符，dp[i][j] = (s[i] == s[j])
     *
     * i - j > 1时： 这个时候当前字符相等还不行，还要他们中间的字符串是回文字符串，
     * 而中间是不是回文字符串，上一轮的遍历中已经知道，
     * 状态转移方程为：dp[i][j] = (s[i] == s[j] && dp[j+1][i-1])
     *
     */
    public static String longestPalindrome2(String s) {
        if (s.equals("") || s == null) {
            return "";
        }
        boolean dp[][] = new boolean[s.length()][s.length()];// 记录上次比较状态
        int left = 0, right = 0;
        int maxLength = 0;
        // 扫描整个字符串，i 一直增大到 s.length
        // 每增大一次 i 表示得到了新的字符串，需要利用 j 判断现在的字符串是否为回文的
        for (int i = 0; i < s.length(); i++) {
            // 每一个单独的字符一定是回文的
            dp[i][i] = true;
            // 判断的办法就是比对当前字符串左右是否对称，需要调整 i、j往中间走
            for (int j = 0; j < i; j++) {
                dp[j][i] =
                        ( s.charAt(i) == s.charAt(j) && (i - j < 2 || dp[j + 1][i - 1]) );
                if (dp[j][i] && maxLength < i - j + 1) {
                    maxLength = i - j + 1;
                    left = j;
                    right = i;
                }
            }
        }
        return s.substring(left, right + 1);
    }

}